package tencent

//中心扩散法，奇数/偶数的形式扩散
//结束条件， 扩散到了左边界/右边界
func longestPalindrome(s string) string {
	subLongestPalindrome(s, 0, len(s))
}

func subLongestPalindrome(s string, start, end int) (left, right int) {
	mid := (start + end) / 2
	//奇数 扩散
	d := 1
	for ; d <= mid; d++ {
		if s[mid-d] != s[mid+d] {
			break
		}
	}
	left, right = mid-d+1, mid+d-1
	if left == start && right == end {
		return
	}
	d = 0
	//偶数
	for true {
		if s[mid-d] != s[mid+d+1] {
			break
		}
	}
	left2, right2 := mid-d+1, mid+d-1
	if right2-left2 > (right - left) {
		left, right = left2, right2
	}
	return
}
